#include<stdio.h>
#include"string.h"
#define n 100
int p_num=0;
int num=0;

struct 
{
    char name[20];
    int address;
    int length;
    int flag;
}free_table[n],work_table[n],temp;

void sort(){
    int i;
    for(i=0;i<num-1;i++)
        for(int j=0;j<num-1;j++)
			if(free_table[j].address>free_table[j+1].address)
			{
				temp=free_table[j];
				free_table[j]=free_table[j+1];
				free_table[j+1]=temp;
			}
		for(i=0;i<p_num-1;i++)
			for(int j=0;j<p_num-i-1;j++)
				if(work_table[j].address>work_table[j+1].address)
				{
					temp=work_table[j];
					work_table[j]=work_table[j+1];
					work_table[j+1]=temp;
				}
}
void merge()
{
	for(int i=0;i<num-1;i++)
	{
		if(free_table[i].address + free_table[i].length==free_table
			[i+1].address)
		{
			if(!free_table[i].flag && !free_table[i+1].flag)
			{
				free_table[i].length+=free_table[i+1].length;
				for(int j=i+1;j<num-1;j++)
					free_table[j]=free_table[j+1];
				i--;
				num--;
			}
		}
	}
}
void output1()
{
	printf("\n空闲区表：\n起始地址  长度\t状态\n");
	for(int i=0; i<num; i++)
		printf("%4d\t %3d\t%3d\n", free_table[i].address, free_table
		       [i].length,free_table[i].flag);
}
void output2()
{
	printf("\n已分配区表：\n起始地址  长度\t状态\t占用作业\n");
	for(int i=0; i<p_num; i++)
		printf("%4d\t%3d\t%3d\t%s\n",work_table[i].address,work_table
		       [i].length,work_table[i].flag,work_table[i].name);
}
void init()
{
	int i;
	printf("\n\t\t<<---!!!@@@最先适应算法@@@!!!--->>\n\n");
	printf("输入空闲区个数：");
	scanf("%d",&num);
	for(i=0; i<num ;i++)
	{
		printf("输入空闲区%d的起始地址和长度：",i);
		scanf ("%d%d", &free_table[i].address, &free_table[i].length);
		free_table[i].flag=0;
	}
	sort();
	merge();
	if(free_table[0].address!=0)
	{
		work_table[p_num].address=0;
		work_table[p_num].length=free_table[0].address;
		work_table[p_num].flag=1;
		strcpy(work_table[p_num].name,"Unknow");
		p_num++;
	}
	for(i=0; i<num-1; i++)
	{
        work_table[p_num].address=free_table[i].address+free_table[i].length;
		work_table[p_num].length=free_table[i+1].address-work_table[p_num].address;
		work_table[p_num].flag=1;
		strcpy(work_table[p_num].name, "Unknow");
		p_num++;
	}
	if(free_table[num-1].address+free_table[num-1].length!=1024)
	{
		work_table[p_num].address=free_table[num-1].address+free_table[num-1].length;
		work_table[p_num].length=1024-work_table[p_num].address;
		work_table[p_num].flag=1;
		strcpy(work_table[p_num].name,"Unknow");
		p_num++;
	}
    sort();
	output1();
	output2();
}
void input()
{
	int i,length;
	char name[20];
	printf("输入作业名称:");
	gets(name);
	printf("输入作业大小:");
	scanf("%d", &length);
	fflush(stdin);
	for(i=0; i<num;i++)
	{
		if(!free_table[i].flag)
		{
			if(length<free_table[i].length)
			{
				work_table[p_num].address=free_table[i].address;
				free_table[i].length=free_table[i].length-length;
				free_table[i].address=free_table[i].address+length;
				strcpy(work_table[p_num].name, name);
				work_table[p_num].flag=1;
				work_table[p_num].length=length;
				p_num++;
				break;
			}
			else if(length==free_table[i].length)
			{
				strcpy(work_table[p_num].name, name);
				work_table[p_num].flag=1;
				work_table[p_num].address=free_table[i].address;
				work_table[p_num].length=free_table[i].length;
				p_num++;
				for(int j=i; j<num; j++)
				{
					free_table[j]=free_table[j+1];
				}
				num--;
				break;
			}
		}
	}
	if(i==num)
	{
		puts("\n无合适空闲区，不能为作业分配内存！\n");
		return;
	}
	sort();
	output1();
	output2();
}
void finish()
{
	char name[20];
	int i;
	printf("输入作业名：");
	gets(name);
	fflush(stdin);
	for(i=0; i<p_num; i++)
	{
		if(!strcmp(name, work_table[i].name))
		{
			free_table[num]=work_table[i];
			free_table[num].flag=0;
			num++;
			sort();
			merge();
			for(int j=i; j<p_num; j++)
				work_table[j]=work_table[j+1];
			p_num--;
			break;
		}
	}
	if(i==p_num)
		puts("\n没有批作业，重新输入！");
	    output1();
		output2();
}
void FIRST_FIT()
{
	init();
	while(1)
	{
		int c;
		printf("\n1.装入作业\n2.撤销作业\n请选择：");
		scanf("%d",&c);
		fflush(stdin);
		if(c==1)
			input();
		else if(c==2)
			finish();
	}
}
int main(void)
{
	FIRST_FIT();
	return 0;
}

